package arithmetic;

/**
 * Created by AJie on 2019/5/22
 * leetcode 动态规划-322 零钱兑换
 * Function :
 */
public class A_31_CoinChange {
    public static void main(String[] args) {
//        Input: coins = [1, 2, 5], amount = 11
//        Output: 3
//        Explanation: 11 = 5 + 5 + 1
//        Input: coins = [2], amount = 3
//        Output: -1
        int[] coins = {1, 2, 5} ;
        int amount = 11;
//        int[] coins = {2} ;
//        int[] coins = {24,311,68,43};
//        int amount = 3076;
//        int res = coinChange(coins,amount);
       int res =  coinChange2(coins,amount);
        System.out.println("res=="+ res);
    }

    public static int coinChange2(int[] coins, int amount) {
        int dp[] = new int[amount+1];
        dp[0] = 0;
        for (int i = 1; i < amount + 1; i++) {
            int dpMin = dp[i] = amount+1;
            for (int j = 0; j < coins.length; j++) {
                int coin = coins[j];
                if (i>=coin){
                    dpMin = Math.min(dp[i-coin]+1,dpMin);
                }
            }
            dp[i] = dpMin;

        }

        return dp[amount]>amount?-1:dp[amount];
    }


    /**
     * 等于楼梯问题
     * 状态定义
     * 状态转移
     * 最优子结构
     * @param coins
     * @param amount
     * @return
     */
    private static int coinChange(int[] coins, int amount) {
        if (amount <= 0){return 0;}
        if(coins.length<1){ return -1; }
        //第 i 天 dp[i] 最少步
        // dp[i] = dp [i-(nums k)] +1
        int [] dp = new int[amount+1];
        for (int i = 0; i <= amount; i++) {
            dp[i]= amount+1;
            if (i==0) {dp[0]=0;}
            for (int j = 0; j < coins.length; j++) {
                int coin = coins[j];
                if (coin<=i){
                    dp[i] = Math.min(dp[i-coin]+1,dp[i]);
                }
            }
        }
        return dp[amount]>amount? -1 : dp[amount];
    }
}
